﻿// 0822train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#include <map>

using namespace std;


/*
 2行整数，第1行表示二叉树的中序遍历，第2行表示二叉树的前序遍历，以空格分割
 8 12 -3 6 -10 9 -7
-3 12 8 6 9 -10 -7

输出
1行整数，表示求和树的中序遍历，以空格分割
0 8 18 -8 0 -17 0
 */
class Solution01
{
public:
    struct TreeNode
    {
        int val, index;
        TreeNode* left = nullptr;
        TreeNode* right = nullptr;

        TreeNode() = default;
        TreeNode(int val) : val(val) {};
        TreeNode(int val, TreeNode*left, TreeNode*right) : val(val),left(left),right(right) {};
    };

    unordered_map<int, int>inorder_map;
    void insertNode(TreeNode*root, TreeNode*node)
    {
        while (root!=node)
        {
            int root_val = root->val;
            int node_val = node->val;

            if (inorder_map[node_val] < inorder_map[root_val])
            {
                if (root->left == nullptr)
                {
                    root->left = node;
                }
                root = root->left;
            }
            else
            {
                if (root->right == nullptr)
                {
                    root->right = node;
                }
                root = root->right;
            }
        }

    }
    TreeNode* buildTree(vector<int>&inorder_vec, vector<int>&preorder_vec)
    {
        for (int i=0; i<inorder_vec.size(); i++)
        {
            int curr_val = inorder_vec[i];
            inorder_map[curr_val] = i;
        }

        TreeNode* root = new TreeNode(preorder_vec[0]);
        
        for (int i=1; i<preorder_vec.size(); i++)
        {
            int curr_val = preorder_vec[i];
            TreeNode* node = new TreeNode(curr_val);
            insertNode(root, node);
        }
        return root;
    }

    TreeNode* buildNew(TreeNode* node)
    {
        if (node==nullptr)
        {
            return nullptr;
        }

        TreeNode* left_node = buildNew(node->left);
        TreeNode* right_node = buildNew(node->right);

        int new_left_val = (left_node == nullptr) ? 0 : left_node->val;
        int new_right_val = (right_node == nullptr) ? 0 : right_node->val;
        int old_left_val = (node->left == nullptr) ? 0 : node->left->val;
        int old_right_val = (node->right == nullptr) ? 0 : node->right->val;

        int curr_val = new_left_val + new_right_val + old_left_val + old_right_val;
        return new TreeNode(curr_val, left_node, right_node);
	    
    }

    void inorder(TreeNode* node)
    {
        if (node == nullptr) return;
        inorder(node->left);
        result.push_back(node->val);
        inorder(node->right);
    }

    void solve01(vector<int>& inorder_vec, vector<int>& preorder_vec)
    {
        TreeNode* root = buildTree(inorder_vec, preorder_vec);
        TreeNode* new_root = buildNew(root);

        inorder(new_root);

        for (int i=0; i<result.size(); i++)
        {
            cout << result[i];
            if (i!=result.size()-1)
            {
                cout << ' ';
            }
        }
    }
private:
    vector<int>result;
};


/*
输入
4
100 200 300 500
1 2
1 3
2 4
输出
700
 */
void solve02(vector<int>&num_vec, vector<pair<int,int>>&linked_vec)
{
    int vec_size = num_vec.size();
    unordered_map<int, vector<int>>child_map;
    unordered_set<int>child_set;
    for (auto&pair_item:linked_vec)
    {
        int key_index = pair_item.first - 1;
        int child_index = pair_item.second - 1;
        child_map[key_index].push_back(child_index);
        child_set.insert(child_index);
    }

    int root = -1;
    for (int i=0;i< vec_size;i++)
    {
        if (child_set.count(i)==0)
        {
            root = i;
        }
    }

    queue<int>bfs_queue;
    bfs_queue.push(root);
    int result = 0;
    while (!bfs_queue.empty())
    {
        int top_node = bfs_queue.front();
        bfs_queue.pop();

        vector<int>child_vec = child_map[top_node];
        int curr_val = num_vec[top_node];
        for (auto&child:child_vec)
        {
            curr_val += num_vec[child];
            bfs_queue.push(child);
        }
        result = max(result, curr_val);
    }
    cout << result;
    //solve02
}

/*
5
b a
c a
d c
e c
f d
c

输出
d
e
f
 */

void solve03(vector<pair<string, string>>&linked_vec, string&search_node)
{
    unordered_map<string, vector<string>>child_map;
    unordered_set<string>child_set;
    for (auto&pair_item:linked_vec)
    {
        string parent = pair_item.second;
        string child = pair_item.first;
        child_map[parent].push_back(child);
        child_set.insert(child);
    }

    string root;
    for (auto&map_item:child_map)
    {
        string p_node = map_item.first;
        if (child_set.count(p_node)==0)
        {
            root = p_node;
        }
    }

    queue<string>bfs_queue;
    vector<string>result_vec;
    bfs_queue.push(search_node);

    while (!bfs_queue.empty())
    {
        string top_node = bfs_queue.front();
        bfs_queue.pop();

        if (top_node!=search_node)
        {
            result_vec.push_back(top_node);
        }

        vector<string>child_vec = child_map[top_node];
        for (auto&child_num:child_vec)
        {
            bfs_queue.push(child_num);
        }

        //while (!bfs_queue.empty())
    }
    sort(result_vec.begin(), result_vec.end());
    for (auto&node:result_vec)
    {
        cout << node << endl;
    }
    //solve03------
}


/*
请完成一个函数，根据输入的数字数组，生成哈夫曼树，并将哈夫曼树按照中序遍历输出。
为了保证输出的二又树中序遍历结果统一，增加以下限制：
二叉树节点中，左节点权值小于等于右节点权值，根节点权值为左右节点权值之和。
当左右节点权值相同时，左子树高度高度小于等于右子树
注意：所有用例保证有效，并能生成哈夫曼树。
输入描述
第一行输入为数组长度，记为N，1<=N<=1000
第二行输入无序数值数组，以空格分割，数值均大于等于1，小于100000

输出描述
输出一个哈夫曼树的中序遍历的数组，数值间以空格分割

输入
5
5 15 40 30 10
输出
40 100 30 60 15 30 5 15 10
 */
class Solution04
{
public:
    struct TreeNode
    {
        int val, height;
        TreeNode* left = nullptr;
        TreeNode* right = nullptr;

        TreeNode() = default;
        TreeNode(int val, int height, TreeNode* left, TreeNode* right) :val(val), height(height), left(left), right(right) {};
    };
    void buildTree(vector<TreeNode*>&node_list)
    {
        while (node_list.size()>1)
        {
            sort(node_list.begin(), node_list.end(), [](TreeNode* a, TreeNode* b)
                {
                    if (a->val == b->val)
                    {
                        return a->height > b->height;
                    }
                    return a->val > b->val;
                });

            TreeNode* left_node = node_list.back(); node_list.pop_back();
            TreeNode* right_node = node_list.back(); node_list.pop_back();

            int new_val = left_node->val + right_node->val;
            int new_height = max(left_node->height, right_node->height) + 1;

            node_list.push_back(new TreeNode(new_val, new_height, left_node, right_node));
        }

        //buildTree
    }

    void inorder(TreeNode* node)
    {
        if (node==nullptr)
        {
            return;
        }
        inorder(node->left);
        result.push_back(node->val);
        inorder(node->right);
    }

    void solve04(vector<int>& tree_vec)
    {
        int vec_size = tree_vec.size();
        vector<TreeNode*>node_list;
        for (int i=0; i<tree_vec.size(); i++)
        {
            int val = tree_vec[i];
            TreeNode* node = new TreeNode(val, 0, nullptr, nullptr);
            node_list.push_back(node);
        }
        buildTree(node_list);
        inorder(node_list[0]);

        for (auto&num:result)
        {
            cout << num << ' ';
        }

        //solve04------
    }
private:
    vector<int>result;
};

/*
 输入
 hello,2,ok,0,bye,0,test,0,one,1,two,1,a,0
 输出
 3
 hello test one
 ok bye two
 a
 */
class Solution05
{
public:
    int curr_index = 0;
    void dfs(vector<pair<string,int>>&tree_vec, int depth)
    {
        pair<string, int>curr_pair = tree_vec[curr_index];
        string curr_str = curr_pair.first;
        int child_count = curr_pair.second;
        //消费当前节点
        curr_index++;

        if (depth - 1 >= result.size())
        {
            vector<string>new_vec = { curr_str };
            result.push_back(new_vec);
        }
        else
        {
            result[depth - 1].push_back(curr_str);
        }

        for (int i = 0; i < child_count; i++)
        {
            //n个子节点，递归调用n次，记得depth+1
            dfs(tree_vec, depth + 1);
        }

    }
    void solve05(vector<string>&origin_vec)
    {
        vector<pair<string, int>>tree_vec;
        int index = 0;
        while (index+1<origin_vec.size())
        {
            string curr_str = origin_vec[index];
            int child_count = stoi(origin_vec[index + 1]);

            pair<string, int>curr_pair = make_pair(curr_str, child_count);
            tree_vec.push_back(curr_pair);
            index += 2;
        }
        //初始高度为1
        while (curr_index<tree_vec.size())
        {
            dfs(tree_vec, 1);
        }

        cout << result.size() << endl;
        for (auto&min_vec:result)
        {
	        for (auto&num:min_vec)
	        {
                cout << num << ' ';
	        }
            cout << '\n';
        }
    }
private:
    vector<vector<string>>result;
};


int main()
{
	{
        string input;
        getline(cin, input);
        vector<string>origin_vec;
        //string input = "hello,2,ok,0,bye,0,test,0,one,1,two,1,a,0";
        stringstream oh_sstream(input);
        string token;
        while (getline(oh_sstream,token,','))
        {
            origin_vec.push_back(token);
        }
        
        Solution05 solu;
        solu.solve05(origin_vec);

        return 0;
	}
/*
5
5 15 40 30 10
*/
	{
        int vec_size;
        cin >> vec_size;
        vector<int>tree_vec(vec_size);
        for (int i=0; i<vec_size; i++)
        {
            cin >> tree_vec[i];
        }

        //vector<int>tree_vec = { 5,15,40,30,10 };
        Solution04 solu;
        solu.solve04(tree_vec);

        return 0;
	}
	{
/*
5
b a
c a
d c
e c
f d
c

输出
d
e
f
 */
        int vec_size;
        cin >> vec_size;
        cin.ignore();

        vector<pair<string, string>>linked_vec(vec_size);
        for (int i=0; i<vec_size; i++)
        {
            string input;
            getline(cin, input);
            int pos = input.find(' ');
            string first = input.substr(0, pos);
            string second = input.substr(pos + 1);

            linked_vec[i] = make_pair(first, second);
        }

        string search_node;
        getline(cin, search_node);
        solve03(linked_vec, search_node);

        return 0;
	}
	{
/*
4
100 200 300 500
1 2
1 3
2 4
 */
        //int vec_size;
        //cin >> vec_size;
        //vector<int>num_vec(vec_size);
        //for (int i=0; i<vec_size; i++)
        //{
        //    cin >> num_vec[i];
        //}

        //cin.ignore();
        //vector<pair<int, int>>linked_vec;

        //string input;
        //while (getline(cin,input))
        //{
        //    if (input.empty())break;
        //    int pos = input.find(' ');

        //    string first = input.substr(0, pos);
        //    string second = input.substr(pos+1);

        //    linked_vec.push_back(make_pair(stoi(first), stoi(second)));
        //}

        vector<int>num_vec = { 100,200,300,500 };
        vector<pair<int, int>>linked_vec = {{1,2},{1,3},{2,4}};
        solve02(num_vec, linked_vec);
        return 0;
	}
    //第1行表示二叉树的中序遍历，第2行表示二叉树的前序遍历
    //8 12 -3 6 -10 9 -7
	//-3 12 8 6 9 -10 -7
    //string inorder_str = "8 12 -3 6 -10 9 -7";
    //string preorder_str = "-3 12 8 6 9 -10 -7";
    string inorder_str, preorder_str;
    getline(cin, inorder_str);
    getline(cin, preorder_str);

    vector<int>inorder_vec;
    vector<int>preorder_vec;

    stringstream inorder_stream(inorder_str);
    stringstream preorder_stream(preorder_str);
    string token;

    while (inorder_stream>>token)
    {
        inorder_vec.push_back(stoi(token));
    }

    while (preorder_stream>>token)
    {
        preorder_vec.push_back(stoi(token));
    }

    Solution01 solu;
    solu.solve01(inorder_vec, preorder_vec);
    
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
